package com.LeeCode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 使用机器人打印字典序最小的字符串
 */

public class Code2434 {
    public static void main(String[] args) {
        String s = "zza";
        System.out.println(new Code2434().robotWithString(s));

    }

    public String robotWithString(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        char[] chars = s.toCharArray();
        int n = chars.length;

        // 构建后缀最小值数组
        char[] suffixMin = new char[n];
        suffixMin[n - 1] = chars[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = (char) Math.min(chars[i], suffixMin[i + 1]);
        }

        StringBuilder res = new StringBuilder();
        int i = 0;

        while (i < n || !stack.isEmpty()) {
            // 只要栈顶字符 <= 当前剩余最小字符，就可以弹出
            while (!stack.isEmpty() && (i >= n || stack.peek() <= suffixMin[i])) {
                res.append(stack.pop());
            }

            if (i < n) {
                stack.push(chars[i++]);
            } else {
                break;
            }
        }

        return res.toString();
    }
}
